class Node:
    def __init__(self, val=-1, lchild=None, rchild=None):
        self.val = val
        self.lchild = lchild
        self.rchild = rchild

class Tree(object):
    def __init__(self, ):
        self.root = Node()
        self.my_queue = []

    def add_node(self, val):
        node = Node(val)
        if self.root.val == -1:
            self.root = node
            self.my_queue.append(self.root)
        else:
            treeNode = self.my_queue[0]
            if treeNode.lchild == None:
                treeNode.lchild = node
                self.my_queue.append(treeNode.lchild)
            else:
                treeNode.rchild = node
                self.my_queue.append(treeNode.rchild)
                self.my_queue.pop(0)

    # 先序遍历
    def pre_order(self, root):
        if root == None:
            return
        print(root.val, end=' ')
        self.pre_order(root.lchild)
        self.pre_order(root.rchild)

    def in_order(self, root):
        if root == None:
            return
        self.pre_order(root.lchild)
        print(root.val, end=' ')
        self.pre_order(root.rchild)

    def post_Order(self, root):
        if root == None:
            return
        self.pre_order(root.lchild)
        self.pre_order(root.rchild)
        print(root.val, end=' ')

    def level_order(self, root):
        queue = []
        queue.append(self.root)
        while queue:
            current_node = queue.pop(0)  # 出队获得当前结点
            print(current_node.val, end=' ')
            if current_node.lchild:
                queue.append(current_node.lchild)
            if current_node.rchild:
                queue.append(current_node.rchild)


if __name__ == '__main__':
    elems = range(10)
    tree = Tree()
    for i in elems:
        tree.add_node(i)
    print("先序遍历：")
    tree.pre_order(tree.root)

    print("\n\n中序遍历：")
    tree.in_order(tree.root)

    print("\n\n后序遍历：")
    tree.post_Order(tree.root)

    print("\n\n层序遍历：")
    tree.level_order(tree.root)
